package 排序算法.归并排序;

import java.util.Arrays;

/**
 * 归并排序
 * 时间复杂度：O(n * log n)
 * 空间复杂度：s(n)
 * 稳定
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr= {8,9,58,5,6,3,5,87,0,5,5};
        mergeSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int l, int r) {
        //边界条件为l>=r 即到了最后一个每个元素都是一个的时候-
        if (l >= r){
            return;
        }
        //每次求取中间的值
        int mid = (l + r) / 2;
        //将这个数组的左边进行一个递归，递归到每个只有一个元素的时候
        mergeSort(arr, l, mid);
        //递归数组右边的区间，直到每个元素为一个值
        mergeSort(arr, mid + 1,r);
        //判断左边的元素是否大于右边，大于就进行一个合并
        if (arr[mid] > arr[mid + 1]){
            merge(arr,l, r, mid);
        }
    }

    private static void merge(int[] arr, int l, int r, int mid) {
        //拷贝原数组，到一个新的数组，否则操作的是源数组，会覆盖原数组的值
        int[] aux = new int[r - l + 1];
        //遍历当前要合并的数组，从l开始到r结束，注意新数组的下标为0-length，当前数组的下标为l-r
        for (int i = l; i <= r ; i++) {
            aux[i - l] = arr[i];
        }

        //k为当前数组的下标，i为拷贝数组的第一个下标，j为分组后的mid+1-l的第二个组的第一个下标
        int k = l;
        int i = 0;
        int j = mid + 1 - l;

        while (true){
            //当要比较的两个数的值超出范围时退出循环
            if (i > mid - l && j > r - l){
                break;
                //当左边的组遍历完了，就直接添加右边组的值，右边的下标++
            }else if (i > mid - l){
                arr[k] = aux[j];
                j++;
                //当右边的组遍历完了，就直接添加左边组的值，左边的下标++
            }else if (j > r - l){
                arr[k] = aux[i];
                i++;
                //如果左边的组的值大于右边的组的值就添加右边组的值，右边组的下标++
            }else if(aux[i] >= aux[j]){
                arr[k] = aux[j];
                j++;
            }else {
                //否则就是右边组的值要大于左边组的值，此时就添加左边组的值，左边的组的下标++
                arr[k] = aux[i];
                i++;
            }
            //k的值始终要++
            k++;
        }

    }
}
